1248. 统计「优美子数组」

Similar Question

Solution Tips

方案一: 滑动窗口

不断右移 right 指针来扩大滑动窗口，使其包含 k 个奇数；

若当前滑动窗口包含了 k 个奇数，则如下「计算当前窗口的优美子数组个数」：

统计第 1 个奇数左边的偶数个数 leftEvenCnt。 这 leftEvenCnt 个偶数都可以作为「优美子数组」的起点，因此起点的选择有 leftEvenCnt + 1 种（因为可以一个偶数都不取，因此别忘了 +1 喔）。

统计第 k 个奇数右边的偶数个数 rightEvenCnt 。 这 rightEvenCnt 个偶数都可以作为「优美子数组」的终点，因此终点的选择有 rightEvenCnt + 1 种（因为可以一个偶数都不取，因此别忘了 +1 喔）。

因此「优美子数组」左右起点的选择组合数为 (leftEvenCnt + 1) * (rightEvenCnt + 1)。

var numberOfSubarrays = function(nums, k) {
    // 要求的是子数组的数目, 得遍历全部的子数组才行呀, 不然怎么知道呢?
    // 滑动窗口, 滑动直至恰好有 k 个奇数, 然后收缩一个, 再继续滑动
    // 这题滑动窗口比前缀和更容易想
    let res = 0;
    let count = 0;
    let left = 0;
    let right = 0;
    while (left <= right && right < nums.length) {
        while (count < k && right < nums.length) {
            if (nums[right] % 2 === 1) {
                count++
            }
            right++;
        }

        if (count !== k) {
            // right 已经扩张到最大了, 都搜集不满, 之后 left 一收缩就更没有了
            return res;
        }

        // 此刻 count === k
        // 继续向右寻找到 right 的边界, 即下一个位置是奇数, 此时是包含这k个奇数的 right 的边界
        let rightEvenCount = 0;
        while (right < nums.length && (nums[right] % 2) == 0) {
            right++;
            rightEvenCount++;
        }
        // 此时 nums[right] 为奇数

        let leftEvenCount = 0;
        // 收缩 left, 直到不等于 k
        while (count === k && left <= right) {
            if (nums[left] % 2 === 1) {
                count--;
            }
            else {
                leftEvenCount++;
            }
            left++;
        }

        res += (leftEvenCount + 1) * (rightEvenCount + 1);
    }

    return res;
};

方案二: 前缀和

计算前缀和数组 arr：遍历原数组，每遍历一个元素，计算当前的前缀和（即到当前元素为止，数组中有多少个奇数）；

对上述前缀和数组，双重循环统计 arr[j] - arr[i] == k 的个数，这样做是 O(N^2) 的（这里会超时哦）。

优化：因此，我们可以像「1. 两数之和」那样使用 HashMap 优化到 O(N)O(N)O(N)，键是「前缀和」，值是「前缀和的个数」（下面代码中具体使用的是 int[] prefixCnt 数组，下标是「前缀和」，值是「前缀和的个数」），因此我们可以遍历原数组，每遍历到一个元素，计算当前的前缀和 sum，就在 res 中累加上前缀和为 sum - k 的个数。

var numberOfSubarrays = function(nums, k) {
    let befores = [0]
    for (let i = 0; i < nums.length; i++) {
        // 奇数
        if (nums[i] % 2 !== 0) {
            befores[i + 1] = befores[i] + 1
        } else {
            befores[i + 1] = befores[i]
        }
    }

    const map = new Map()
    map.set(0, 1)

    let cnt = 0
    for (let i = 1; i < befores.length; i++) {
        const dValue = befores[i] - k
        if (map.has(dValue)) {
            cnt += map.get(dValue)
        }
        map.set(befores[i], map.get(befores[i]) ? map.get(befores[i]) + 1 : 1)
    }

    return cnt
};